package top75

import (
	"slices"
	"sort"
)

func reverseVowels(s string) string {
	var res = make([]byte, len(s))
	for i := 0; i < len(s); i++ {
		res[i] = s[i]
	}
	var left = 0
	var right = len(s) - 1
	for left < right {
		for left < right && !targetLetter(s[left]) {
			left++
		}
		for left < right && !targetLetter(s[right]) {
			right--
		}
		if left < right {
			res[left], res[right] = res[right], res[left]
			left++
			right--
		}
	}
	return string(res)
}

func targetLetter(s byte) bool {
	switch s {
	case 'a':
		return true
	case 'e':
		return true
	case 'i':
		return true
	case 'o':
		return true
	case 'u':
		return true
	case 'A':
		return true
	case 'E':
		return true
	case 'I':
		return true
	case 'O':
		return true
	case 'U':
		return true
	default:
		return false
	}
}
func findMaxAverage(nums []int, k int) float64 {
	var left = 0
	var right = 0
	var sum = 0
	for right < k {
		sum += nums[right]
		right++
	}

	var maxSum = sum
	for right < len(nums) {
		sum += nums[right] - nums[left]
		right++
		left++
		if sum > maxSum {
			maxSum = sum
		}
	}
	return float64(maxSum) / float64(k)
}
func closeStrings(word1 string, word2 string) bool {
	if len(word1) != len(word2) {
		return false
	}
	var c1 = make([]int, 26)
	var c2 = make([]int, 26)
	for i := 0; i < len(word1); i++ {
		c1[word1[i]-'a']++
	}
	for i := 0; i < len(word2); i++ {
		c2[word2[i]-'a']++
	}
	for i := 0; i < 26; i++ {
		if c1[i] > 0 && c2[i] == 0 {
			return false
		} else if c1[i] == 0 && c2[i] == 0 {
			return false
		}
	}
	slices.Sort(c1)
	slices.Sort(c2)
	for i := 0; i < 26; i++ {
		if c1[i] != c2[i] {
			return false
		}
	}
	return true
}

/**
 * @description: 735.小行星碰撞
 * @keyword:
 * @author: kami
 * @date 2024/3/1 9:23
 */
func asteroidCollision(asteroids []int) []int {
	var res = []int{asteroids[0]}
	for i := 1; i < len(asteroids); i++ {
		if len(res) == 0 {
			res = append(res, asteroids[i])
			continue
		}
		if crash(asteroids[i], res[len(res)-1]) {
			res = append(res, asteroids[i])
		} else {
			var curVal = asteroids[i]
			for len(res) > 0 && crash(res[len(res)-1], curVal) {
				if abs(curVal) > abs(res[len(res)-1]) {
					res = res[:len(res)-1]
				} else if abs(curVal) < abs(res[len(res)-1]) {
					curVal = res[len(res)-1]
					res = res[:len(res)-1]
				} else {
					res = res[:len(res)-1]
					curVal = 0
				}
			}
			if curVal != 0 {
				res = append(res, curVal)
			}
		}
	}
	return res
}

func crash(a, b int) bool {
	if a > 0 && b < 0 {
		return true
	}
	return false
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	var count = 1
	var end = intervals[0][1]
	for i := 0; i < len(intervals); i++ {
		if intervals[i][0] >= end {
			count++
			end = intervals[i][1]
		}
	}
	return len(intervals) - count
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	var dumpHead = &ListNode{Next: head}
	var pre = dumpHead
	var cur = head
	for cur != nil {
		var tempHead = cur
		var tail = cur
		var idx = 1
		for idx < k {
			tail = tail.Next
			if tail == nil {
				return dumpHead.Next
			}
			idx++
		}
		reverse(pre, tempHead, tail)
		pre = tempHead
		cur = tempHead.Next
	}
	return dumpHead.Next
}

func reverse(pre, head, tail *ListNode) {
	var next = tail.Next
	var cur = head
	var curPre *ListNode
	for cur != next {
		var curNext = cur.Next
		cur.Next = curPre
		curPre = cur
		cur = curNext
	}
	pre.Next = tail
	head.Next = next
}

func findMaxAverage1(nums []int, k int) float64 {
	var left = 0
	var right = 0
	var sum = 0
	for right < k {
		sum += nums[right]
		right++
	}
	var max float64 = 0.0
	var ava = float64(sum) / float64(k)
	if ava > max {
		max = ava
	}
	for right < len(nums) {
		sum = sum + nums[right] - nums[left]
		ava = float64(sum) / float64(k)
		if ava > max {
			max = ava
		}
		left++
		right++
	}
	return max
}

func orangesRotting(grid [][]int) int {
	var cnt int
	var row []int
	var col []int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 1 {
				cnt++
			} else if grid[i][j] == 2 {
				row = append(row, i)
				col = append(col, j)
			}
		}
	}
	if cnt == 0 {
		return 0
	}
	if len(row) == 0 {
		return -1
	}
	var res int
	for len(row) > 0 {
		res++
		var size = len(row)
		for x := 0; x < size; x++ {
			var i = row[x]
			var j = col[x]
			if isFresh(grid, i-1, j) {
				grid[i-1][j] = 2
				row = append(row, i-1)
				col = append(col, j)
				cnt--
			}
			if isFresh(grid, i+1, j) {
				grid[i+1][j] = 2
				row = append(row, i+1)
				col = append(col, j)
				cnt--
			}
			if isFresh(grid, i, j-1) {
				grid[i][j-1] = 2
				row = append(row, i)
				col = append(col, j-1)
				cnt--
			}
			if isFresh(grid, i, j+1) {
				grid[i][j+1] = 2
				row = append(row, i)
				col = append(col, j+1)
				cnt--
			}
		}
		if cnt == 0 {
			return res
		}
		if len(row) == size {
			return -1
		}
		row = row[size:]
		col = col[size:]
	}
	return res

}

func isFresh(grid [][]int, i, j int) bool {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[i]) || grid[i][j] != 1 {
		return false
	}
	return true
}
